

//分割链表，以x值进行分割，比他小的在左边，大的在右面，不需要保证顺序
#include <iostream>

struct ListNode
{
    int val;
    ListNode* next;
};

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if (head == nullptr)
            return nullptr;

        ListNode* little = head;
        ListNode* big = head;
        while (little != nullptr && big != nullptr) 
        {
            // 先找一个比x大的位置
            while (little != nullptr && little->val < x) 
                little = little->next;
            // 如果没有比x大的，就返回
            if (little == nullptr)
                break;

            // 找一个比x小的位置
            big = little->next;
            while (big != nullptr && big->val>= x) 
                big = big->next;
            // 如果没有比x小的，也返回
            if(big == nullptr)
                break;

            //交换
            std::swap(little->val, big->val);
            little = little->next;
            big = big->next;
        }
        return head;
    }
};